/*!
 * # [975.奇偶跳](https://leetcode.cn/problems/odd-even-jump/description/)
 *
 * @lc app=leetcode.cn id=975 lang=rust
 * 
 * ## 难度
 * - Hard (45.01%)
 * - Likes:    131
 * - Dislikes: 0
 * - Total Accepted:    3.3K
 * - Total Submissions: 7.4K
 * - Testcase Example:  '[10,13,12,14,15]'
 *
 * ## 描述
 * 
 * 给定一个整数数组 A，你可以从某一起始索引出发，跳跃一定次数。在你跳跃的过程中，第 1、3、5... 次跳跃称为奇数跳跃，而第 2、4、6...
 * 次跳跃称为偶数跳跃。
 *
 * 你可以按以下方式从索引 i 向后跳转到索引 j（其中 i < j）：
 *
 * 在进行奇数跳跃时（如，第 1，3，5... 次跳跃），你将会跳到索引 j，使得 A[i] <= A[j]，A[j]
 * 是可能的最小值。如果存在多个这样的索引 j，你只能跳到满足要求的最小索引 j 上。
 * 在进行偶数跳跃时（如，第 2，4，6... 次跳跃），你将会跳到索引 j，使得 A[i] >= A[j]，A[j]
 * 是可能的最大值。如果存在多个这样的索引 j，你只能跳到满足要求的最小索引 j 上。
 * （对于某些索引 i，可能无法进行合乎要求的跳跃。）
 *
 *
 * 如果从某一索引开始跳跃一定次数（可能是 0 次或多次），就可以到达数组的末尾（索引 A.length - 1），那么该索引就会被认为是好的起始索引。
 *
 * 返回好的起始索引的数量。
 *
 * ## 示例 1：
 * - 输入：[10,13,12,14,15]
 * - 输出：2
 * - 解释：
 *   - 从起始索引 i = 0 出发，我们可以跳到 i = 2，（因为 A[2] 是 A[1]，A[2]，A[3]，A[4] 中大于或等于 A[0]
 * 的最小值），然后我们就无法继续跳下去了。
 *   - 从起始索引 i = 1 和 i = 2 出发，我们可以跳到 i = 3，然后我们就无法继续跳下去了。
 *   - 从起始索引 i = 3 出发，我们可以跳到 i = 4，到达数组末尾。
 *   - 从起始索引 i = 4 出发，我们已经到达数组末尾。
 * 总之，我们可以从 2 个不同的起始索引（i = 3, i = 4）出发，通过一定数量的跳跃到达数组末尾。
 *
 *
 * ## 示例 2：
 * - 输入：[2,3,1,1,4]
 * - 输出：3
 * - 解释：
 * 从起始索引 i=0 出发，我们依次可以跳到 i = 1，i = 2，i = 3：
 *
 * 在我们的第一次跳跃（奇数）中，我们先跳到 i = 1，因为 A[1] 是（A[1]，A[2]，A[3]，A[4]）中大于或等于 A[0] 的最小值。
 *
 * 在我们的第二次跳跃（偶数）中，我们从 i = 1 跳到 i = 2，因为 A[2] 是（A[2]，A[3]，A[4]）中小于或等于 A[1]
 * 的最大值。A[3] 也是最大的值，但 2 是一个较小的索引，所以我们只能跳到 i = 2，而不能跳到 i = 3。
 *
 * 在我们的第三次跳跃（奇数）中，我们从 i = 2 跳到 i = 3，因为 A[3] 是（A[3]，A[4]）中大于或等于 A[2] 的最小值。
 *
 * 我们不能从 i = 3 跳到 i = 4，所以起始索引 i = 0 不是好的起始索引。
 *
 * 类似地，我们可以推断：
 * 从起始索引 i = 1 出发， 我们跳到 i = 4，这样我们就到达数组末尾。
 * 从起始索引 i = 2 出发， 我们跳到 i = 3，然后我们就不能再跳了。
 * 从起始索引 i = 3 出发， 我们跳到 i = 4，这样我们就到达数组末尾。
 * 从起始索引 i = 4 出发，我们已经到达数组末尾。
 * 总之，我们可以从 3 个不同的起始索引（i = 1, i = 3, i = 4）出发，通过一定数量的跳跃到达数组末尾。
 *
 *
 * ## 示例 3：
 * - 输入：[5,1,3,4,2]
 * - 输出：3
 * - 解释：
 * 我们可以从起始索引 1，2，4 出发到达数组末尾。
 *
 *
 * ## 提示：
 * - 1 <= A.length <= 20000
 * - 0 <= A[i] < 100000
 */

// @lc code=start
use std::collections::BTreeMap;

impl Solution {
    /// ## 解题思路
    /// - 动态规划+BTreeMap
    pub fn odd_even_jumps(arr: Vec<i32>) -> i32 {
        let mut good_count = 1; // 好索引的计数，最后一个总是可以到达，所以至少为1
        let mut odd = vec![false; arr.len()]; //每个索引位置是否经过奇数步跳跃到达终点；
        let mut even = vec![false; arr.len()]; //每个索引位置是否经过偶数步跳跃到达终点；
        *odd.last_mut().unwrap() = true;
        *even.last_mut().unwrap() = true;

        let mut map = BTreeMap::new(); //
        map.insert(*arr.last().unwrap(), arr.len() - 1);

        for i in (0..arr.len() - 1).rev() {
            let from = arr[i];
            // 在当前数字后面，存在>=当前数字的可跳数字
            if let Some((_, jump_index)) = map.range(from..).next() {
                // 当前位置可进行奇数跳跃，是否能抵达终点和下一个偶数起跳点是否能达到终点一样；
                odd[i] = even[*jump_index];
            }
            // 在当前数字后面，存在<=当前数字的可跳数字
            if let Some((_, jump_index)) = map.range(..=from).next_back() {
                // 当前位置可进行偶数跳跃，是否能抵达终点和下一个奇数起跳点是否能达到终点一样；
                even[i] = odd[*jump_index];
            }
            //如果当前位置可通过奇数起跳到达终点
            if odd[i] {
                good_count += 1; //则好的起始索引数量+1
            }
            //记录当前数字和索引
            map.insert(from, i);
        }
        good_count
    }
}
// @lc code=end
struct Solution;

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test() {
        assert_eq!(Solution::odd_even_jumps(vec![5, 1, 3, 4, 2]), 3);
    }
}
